package com.leetcode.ask;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName RandomPointerLinkedList
 * @Description 138. 复制带随机指针的链表
 * 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
 * <p>
 * 要求返回这个链表的 深拷贝。 
 * <p>
 * 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
 * <p>
 * val：一个表示 Node.val 的整数。
 * random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
 *  
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 * <p>
 * 输入：head = [[1,1],[2,1]]
 * 输出：[[1,1],[2,1]]
 * <p>
 * 输入：head = [[3,null],[3,0],[3,null]]
 * 输出：[[3,null],[3,0],[3,null]]
 * <p>
 * 输入：head = []
 * 输出：[]
 * 解释：给定的链表为空（空指针），因此返回 null。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author liyucheng
 * @Date 2020/10/13 11:52 上午
 * @Version 1.0
 **/
public class RandomPointerLinkedList {

    private static class Node {
        private int val;
        private Node next;
        private Node random;

        public Node(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public Node getRandom() {
            return random;
        }

        public void setRandom(Node random) {
            this.random = random;
        }
    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node newHead = head;
        Map<Node, Node> map = new HashMap<>();
        while (newHead != null) {
            if (!map.containsKey(newHead)) {
                Node copyNode = new Node(newHead.val);
                map.put(newHead, copyNode);
            }
            if (newHead.random != null) {
                Node randomNode = newHead.random;
                if (!map.containsKey(randomNode)) {

                    Node copyRandomNode = new Node(randomNode.val);
                    map.put(randomNode, copyRandomNode);
                }
                map.get(newHead).random = map.get(randomNode);
            }
            newHead = newHead.next;
        }
        newHead = head;
        while (newHead != null){
            map.get(newHead).next = map.get(newHead.next);
            newHead = newHead.next;
        }
        return map.get(head);
    }

    public static void main(String[] args) {

    }
}
